import java.util.ArrayList;
import java.util.List;

/**
 * 给定一个单词数组和一个长度 maxWidth，重新排版单词，使其成为每行恰好有 maxWidth 个字符，且左右两端对齐的文本。
 * <p>
 * 你应该使用“贪心算法”来放置给定的单词；也就是说，尽可能多地往每行中放置单词。必要时可用空格 ' ' 填充，使得每行恰好有 maxWidth 个字符。
 * <p>
 * 要求尽可能均匀分配单词间的空格数量。如果某一行单词间的空格不能均匀分配，则左侧放置的空格数要多于右侧的空格数。
 * <p>
 * 文本的最后一行应为左对齐，且单词之间不插入额外的空格。
 * <p>
 * 说明:
 * <p>
 * 单词是指由非空格字符组成的字符序列。
 * 每个单词的长度大于 0，小于等于 maxWidth。
 * 输入单词数组 words 至少包含一个单词。
 * 示例:
 * <p>
 * 输入:
 * words = ["This", "is", "an", "example", "of", "text", "justification."]
 * maxWidth = 16
 * 输出:
 * [
 *    "This    is    an",
 *    "example  of text",
 *    "justification.  "
 * ]
 * 示例 2:
 * <p>
 * 输入:
 * words = ["What","must","be","acknowledgment","shall","be"]
 * maxWidth = 16
 * 输出:
 * [
 *   "What   must   be",
 *   "acknowledgment  ",
 *   "shall be        "
 * ]
 * 解释: 注意最后一行的格式应为 "shall be    " 而不是 "shall     be",
 *      因为最后一行应为左对齐，而不是左右两端对齐。
 * 第二行同样为左对齐，这是因为这行只包含一个单词。
 * 示例 3:
 * <p>
 * 输入:
 * words = ["Science","is","what","we","understand","well","enough","to","explain",
 *          "to","a","computer.","Art","is","everything","else","we","do"]
 * maxWidth = 20
 * 输出:
 * [
 *   "Science  is  what we",
 * "understand      well",
 *   "enough to explain to",
 *   "a  computer.  Art is",
 *   "everything  else  we",
 *   "do                  "
 * ]
 */
class Solution {

    public static void main(String[] args) {
        // List<String> result = fullJustify(new String[]{"This", "is", "an", "example", "of", "text", "justification."}, 16);
        // List<String> result = fullJustify(new String[]{"What", "must", "be", "acknowledgment", "shall", "be"}, 16);
        // List<String> result = fullJustify(new String[]{"Science", "is", "what", "we", "understand", "well", "enough", "to", "explain", "to", "a", "computer.", "Art", "is", "everything", "else", "we", "do"}, 20);
        // List<String> result = fullJustify(new String[]{"Listen", "to", "many,", "speak", "to", "a", "few."}, 6);
        List<String> result = fullJustify(new String[]{"The", "important", "thing", "is", "not", "to", "stop", "questioning.", "Curiosity", "has", "its", "own", "reason", "for", "existing."}, 17);
        for (int i = 0; i < result.size(); i++) {
            System.out.println(result.get(i));
        }
        for (int i = 0; i < result.size(); i++) {
            System.out.println(result.get(i).length());
        }
    }

    public static List<String> fullJustify(String[] words, int maxWidth) {
        List<String> result = new ArrayList<String>();
        // 定义每一行需要的单词的开始位置和结束位置
        int start = 0, end = 0;
        // 定义当前剩余
        int left = maxWidth;
        for (int i = 0; i < words.length; i++) {
            if (words[i].length() < left) {
                end = i;
                if (i == words.length - 1) {
                    // 如果当前是最后一个单词了，需要特殊处理
                    StringBuilder sb = new StringBuilder();
                    for (int j = start; j < end; j++) {
                        sb.append(words[j]).append(" ");
                    }
                    sb.append(words[i]);
                    int more = maxWidth - sb.length();
                    for (int j = 0; j < more; j++) {
                        sb.append(" ");
                    }
                    result.add(sb.toString());
                } else {
                    // 每个单词至少需要一个空格
                    left -= words[i].length() + 1;
                }
            } else if (words[i].length() == left) {
                StringBuilder sb = new StringBuilder();
                if (i != start) {
                    for (int j = start; j <= end; j++) {
                        sb.append(words[j]).append(" ");
                    }
                }
                sb.append(words[i]);
                start = i + 1;
                end = start;
                left = maxWidth;
                result.add(sb.toString());
            } else {
                // 如果放不下了
                StringBuilder sb = new StringBuilder();
                if (end == start) {
                    // 然后只是一个单词
                    sb.append(words[start]);
                    for (int k = 0; k <= left; k++) {
                        sb.append(" ");
                    }
                } else {
                    // 剩余的空格
                    int blank = left + end - start + 1;
                    // 最小间隔
                    int min = blank / (end - start);
                    int more = blank % (end - start);
                    for (int j = start; j <= end; j++) {
                        sb.append(words[j]).append(more-- > 0 ? " " : "");
                        for (int k = 0; j < end && k < min; k++) {
                            sb.append(" ");
                        }
                    }
                }
                result.add(sb.toString());
                // 处理完成后
                // 开始和结束都需要变成当前的后一个
                start = i;
                end = start;
                // 当前不算，重新开始
                i--;
                // 重置剩余
                left = maxWidth;
            }
        }
        return result;
    }

}